package com.test.leetcode;

import java.util.Arrays;

/**
 * @author sujiafa
 * @date 2025/1/25
 */
public class n1137_第N个泰波那契数 {

    public int tribonacci(int n) {
        // 用数组保存求解过的结果
        int[] memory = new int[n + 1];
        return tribonacci(n, memory);
    }

    private int tribonacci(int n, int[] memory) {

        if (n == 0) {
            return 0;
        } else if (n == 1 || n == 2) {
            return 1;
        }

        // 已经计算过
        if (memory[n] != 0) {
            return memory[n];
        }

        int result = tribonacci(n - 1, memory) + tribonacci(n - 2, memory) + tribonacci(n - 3, memory);
        memory[n] = result;
        return result;
    }
}
